#!/usr/bin/python 

import sys

class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)
 
class FlowNetwork(object):
    def __init__(self, path_file):
	fd = None
	self.adj = {}
	self.flow = {}
	try:
		fd = open(path_file)
	except(IOerror):
		print "no existe el archivo a procesar"
		sys.exit(1)
	try:
		self.add_vertex("s")
		self.add_vertex("t")
		lines = fd.readlines()
		elements = map(lambda s: s.replace("\n", ""), filter(lambda s: s != "\n", lines))
		self.n,self.m = map(lambda s: int(s),  elements.pop(0).split(","))
		Cn = map(lambda s: int(s), elements.pop(0). split(","))
		Pn = map(lambda s: int(s), elements.pop(0). split(","))
		for element in elements:
			task, nadjs = element.split(":")
			adjs = nadjs.split(",")
			self.add_vertex("T"+task)
			for adj in adjs:
				if adj not in self.adj["s"]:
					self.add_vertex("A"+adj)
					self.add_edge("A"+adj, "t", Cn[int(adj)-1])
				self.add_edge("T"+task, "A"+adj, float("inf"))
			self.add_edge("s","T"+task, Pn[int(task)-1])
		fd.close() 
	except:
		print "error construyendo la red de transporte. Archivo corrupto"
		sys.exit(1)

    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and not (edge,residual) in path:
                result = self.find_path( edge.sink, sink, path + [(edge,residual)] ) 
                if result != None:
                    return result
 
    def max_flow(self, source = "s", sink = "t"):
        path = self.find_path(source, sink, [])
        while path != None:
            flow = min(res for edge,res in path)
            for edge,res in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
#	print [self.flow[edge] for edge in self.get_edges(source)]
        return sum(self.flow[edge] for edge in self.get_edges(source))
    
    def __repr__(self):
	rep = []
	inv_edges = [ s.sink for s in self.get_edges("t") if s.redge.capacity == self.flow[s.redge] ]
	for inv_edge in inv_edges:
		for edge in filter(lambda s: s.capacity == 0, self.get_edges(inv_edge)):
			rep.append(edge.sink)
	return " - ".join(rep)
	
try:
	fl = FlowNetwork(sys.argv[1])
#	fl.max_flow()
	print "gasto maximo: " + str(fl.max_flow())
	print "proyectos a realizar : " + str(fl)
except:
	print "argumentos incorrectos"
